package offer

import (
	. "GoLeetcode/common"
	"math"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)

解：dp[i]表示金额为i，通过coins中的硬币进行组合能组成i的最少硬币数
	// dp[i]初始化时为math.MaxInt32, 所以求Min时不可能会比math.MaxInt32还大
	dp[i] = Min(dp[i], 1+dp[i-coin])

	注意：当dp[amount] != math.MaxInt32时，说明无法组合
*/

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = math.MaxInt32
	}
	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] = Min(dp[i], 1+dp[i-coin])
			}
		}
	}
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}